#include <stdio.h>
#include <stdlib.h>

#define MAXJUNCOES 1010
#define INTMAX 2147483646

//Cria a matriz de custos e caminhos
int custos[MAXJUNCOES][MAXJUNCOES]; //matriz que guarda a distancia de cada rua
int caminhos[MAXJUNCOES][MAXJUNCOES]; //matriz que guarda a menor distancia entre cada esquina

//Funcao que calcula o caminho com o menor custo de um ponto ao outro
int Dijkstra(int ori, int origem, int vertices){

    int menor, i, j;
    int vdijs[2][MAXJUNCOES];
    int visitado[MAXJUNCOES];

    for (i=0; i < vertices; i++) {
        visitado[i] = 0;
        vdijs[0][i] = INTMAX; /* guarda o custo */
        vdijs[1][i] = -1; /* vetor de antecedencia */
    }

    vdijs[0][origem] = 0;
    vdijs[1][origem] = origem;

    for (i=0; i < vertices; i++) {
        for (j=0; j< vertices; j++) {
            if (custos[origem][j])
                if (vdijs[0][j] > vdijs[0][origem] + custos[origem][j]) {
                    vdijs[0][j] = vdijs[0][origem] + custos[origem][j];
                    vdijs[1][j] = origem;
                }
            }

        visitado[origem] = 1;
        menor = origem;

        for (j=0; j < vertices; j++) {
            if (!visitado[j] && vdijs[0][j] != INTMAX) {
                if (menor == origem) {
                menor = j;
                } else if (vdijs[0][j] < vdijs[0][menor]) {
                menor = j;
                }
            }
        }

    origem = menor;
    }

    for (i=0; i < vertices; i++) {
       caminhos[ori][i] = vdijs[0][i];
       caminhos[i][ori] = vdijs[0][i];
    }

    return 0;
}

int main()
{

    int n,m,i,j, juncao, total;
    int maior = 0;

    // Recebe o numero de juncoes n e o numero de ruas m
    scanf("%d %d ", &n, &m );
    //printf(" N = %i, M = %i\n", n, m);

    //Verifica se n esta entre 2 e MAXJUNCOES
    if ( n < 2 || n > MAXJUNCOES){
        printf("O valor de n deve estar entre 2 < n < MAXJUNCOES\n");
        return 1;
    }

    //Verifica se m entre (n-1) < m < ((n(n-1))/2)
    if ( m < (n-1) || m > ((n*(n-1))/2) ) {
        printf("O valor de m deve estar entre (n-1) < m < ((n(n-1))/2)) \n");
        return 1;
    }

    //Matriz que recebe as linhas das ruas
    int ruas[3][m];

    //Recebe Ai e Bi (juncao) e o custo Wi
    for (i=0; i<m; i++){
    scanf("%d %d %d", &ruas[0][i], &ruas[1][i], &ruas[2][i] );
    }

    //Inicializa a matriz com zero: zero signinifica que nao ha juncao entreas ruas
    memset(custos, 0, sizeof(int)*n*n);

    //Monta a matriz de custos a partir da matriz das ruas
    for (i=0; i<m; i++){
        int a = ruas[0][i];
        int b = ruas[1][i];
        int custo = ruas[2][i];
        custos[a-1][b-1] = custo;
        custos[b-1][a-1] = custo;
    }

    //Monta a matriz dos custos dos melhores caminhos de um vertice para o outro
    for(i=0; i<n; i++){
        Dijkstra(i, i, n);
    }

    //encontra o valor maximo de cada linha e verifica se e menor que o atual
    maior = INTMAX;
    int max;
    for(i=0; i<n; i++){
        max = 0;
        for(j=0; j<n; j++){
            if (max < caminhos[i][j])
                max = caminhos[i][j];
        }
        if (max < maior){
            maior = max;
            juncao = i;
        }
    }


    //Imprime o resultado
    printf("Maior distancia: %d\n", maior);


    return 0;
}
